package org.example.myleet.simulation;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.JsonUtils;
import org.example.myleet.Utils.ListNode;

import java.util.*;
import java.util.stream.Collectors;

public class SimulationSolution {

    //面试题 01.09. 字符串轮转
    public boolean isFlipedString0109(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        if (s1.length() == 0) {
            return true;
        }
        int n = s1.length();
        boolean odd = (n & 1) == 1;
        String s1HalfPrefix = s1.substring(0, n / 2);
        String s1HalfSuffix = s1.substring(odd ? (n / 2 + 1) : (n / 2), n);
        if (!isFlipedString0109(s1, s2, s1HalfPrefix, n, n /2)) {
            return isFlipedString0109(s1, s2, s1HalfSuffix, n, 0);
        }
        return true;
    }
    private boolean isFlipedString0109(String s1, String s2, String s1Half, int n, int i) {
        int start = s2.indexOf(s1Half);
        if (start < 0) {
            return false;
        }
        int j = start + n / 2;
        while (j != start) {
            if (j >= n) {
                j %= n;
            }
            if (s1.charAt(i) != s2.charAt(j)) {
                return false;
            }
            ++i;
            ++j;
        }
        return true;
    }

    //p6
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        int period = numRows * 2 - 2;
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; ++i) {
            rows[i] = new StringBuilder();
        }
        int i = 0, n = s.length(), ri;
        char[] charArr = s.toCharArray();
        while (i < n) {
            char c = charArr[i];
            int j = i % period;
            if (j < numRows) {
                ri = j;
            } else {
                ri = period - j;
            }
            rows[ri].append(c);
            ++i;
        }
        StringBuilder sb = new StringBuilder();
        for (i = 0; i < numRows; ++i) {
            sb.append(rows[i]);
        }
        return sb.toString();
    }

    //p7
    public int reverse(int x) {
        if (x == 0) {
            return 0;
        }
        List<Integer> numbers = new ArrayList<>();
        boolean negative = x < 0;
        if (negative) {
            x = -x;
        }
        while (x > 0) {
            numbers.add(x - x / 10 * 10);
            x /= 10;
        }
        int res = 0;
        for (int number : numbers) {
            if (res * 10 / 10 < res) {
                return 0;
            }
            res *= 10;
            if (res + number < res) {
                return 0;
            }
            res += number;
        }
        if (negative) {
            res = -res;
        }
        return res;
    }

    //p9
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        String numberStr = Integer.toString(x);
        char[] charArr = numberStr.toCharArray();
        int l = 0, r = charArr.length - 1;
        while (l < r) {
            if (charArr[l] != charArr[r]) {
                return false;
            }
            ++l;
            --r;
        }
        return true;
    }

    //p12
    /**
     * 将每一个位的0～9情况列出来，获取到位以及数字后可以直接得到该位转换结果
     */
    private static String[] THOUSANDS = {"", "M", "MM", "MMM"};
    private static String[] HUNDREDS = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    private static String[] TENS = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    private static String[] DIGITS = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    public String intToRoman(int num) {
        StringBuilder reply = new StringBuilder();
        int n = num;
        int base = 1000;
        while (n > 0) {
            //获取当前位的数字
            int t = n / base;
            if (t > 0) {
                //转换该位数字
                reply.append(getDigits(base)[t]);
            }
            //数字去除最左边的位
            n %= base;
            //数位右移
            base /= 10;
        }
        return reply.toString();
    }
    /**
     * 根据数位获取对应的转换数字集合
     */
    private String[] getDigits(int base) {
        switch (base) {
            case 1000: return THOUSANDS;
            case 100: return HUNDREDS;
            case 10: return TENS;
            case 1: return DIGITS;
            default: throw new RuntimeException("");
        }
    }

    //p19
    /**
     * 放入数组中避开位置查找，简单暴力
     * 1ms
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> nodeArray = new ArrayList<>();
        ListNode curNode = head;
        while (curNode != null) {
            nodeArray.add(curNode);
            curNode = curNode.next;
        }
        int len;
        if ((len = nodeArray.size()) == n) {
            if (1 == n) {
                //只有一个数，直接返回null
                return null;
            }
            //倒数第n个是头，直接从第二个返回就是删除了的
            return nodeArray.get(1);
        } else {
            ListNode node = nodeArray.get(len - n - 1);
            node.next = node.next.next;
            return head;
        }
    }

    //p38
    public String countAndSay(int n) {
        int epoch = 1;
        StringBuilder sb1 = new StringBuilder("1");
        StringBuilder sb2 = new StringBuilder();
        while (n > epoch) {
            int idx = 0;
            char c1 = sb1.charAt(idx++);
            int count = 1;
            while (idx < sb1.length()) {
                char c2 = sb1.charAt(idx++);
                if (c2 == c1) {
                    ++count;
                } else {
                    sb2.append(count).append(c1);
                    c1 = c2;
                    count = 1;
                }
            }
            sb2.append(count).append(c1);
            sb1 = sb2;
            sb2 = new StringBuilder();
            ++epoch;
        }
        return sb1.toString();
    }

    /**
     * p54. 螺旋矩阵
     * 0 ms
     * 每走完一边就移动对应的指针，以去除已经扫描的行列
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        //各限位指针，top-顶边界，bottom-底边界，left-左边界，right-右边界
        int top = 0, bottom = matrix.length-1, left = 0, right = matrix[0].length-1;
        List<Integer> result = new ArrayList<>(bottom * right);
        while (top <= bottom && left <= right) {
            //先进行向右和向下的扫描，再检查自右向左，自下向上的行列还有没有未扫描到的，未扫描的话就继续扫描
            for (int j=left; j<=right; ++j) {
                result.add(matrix[top][j]);
            }
            ++top;
            for (int i=top; i<=bottom; ++i) {
                result.add(matrix[i][right]);
            }
            --right;
            if (top <= bottom) {
                for (int j = right; j >= left; --j) {
                    result.add(matrix[bottom][j]);
                }
                --bottom;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; --i) {
                    result.add(matrix[i][left]);
                }
                ++left;
            }
        }
        return result;
    }

    /**
     * p59. 螺旋矩阵 II
     * 0 ms
     * 与p54题目几乎一样，只不过是填值，都是一样螺旋顺序扫描
     */
    public int[][] generateMatrix(int n) {
        int[][] reply = new int[n][n];
        //各限位指针，top-顶边界，bottom-底边界，left-左边界，right-右边界
        int top = 0, bottom = n-1, left = 0, right = n-1, count = 1;
        while (top <= bottom && left <= right) {
            //先进行向右和向下的扫描，再检查自右向左，自下向上的行列还有没有未扫描到的，未扫描的话就继续扫描
            for (int j=left; j<=right; ++j) {
                reply[top][j] = count++;
            }
            ++top;
            for (int i=top; i<=bottom; ++i) {
                reply[i][right] = count++;
            }
            --right;
            if (top <= bottom) {
                for (int j = right; j >= left; --j) {
                    reply[bottom][j] = count++;
                }
                --bottom;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; --i) {
                    reply[i][left] = count++;
                }
                ++left;
            }
        }
        return reply;
    }

    //68【模拟】文本左右对齐
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new LinkedList<>();
        //cursor-当前单词，n-所有词的数量，len-lineWords里面的词使用1个空格的情况下连接起来的长度
        int cursor = 0, n = words.length, len = 0;
        //一行使用的单词，及一行单词的数组长度计数
        String[] lineWords = new String[maxWidth];
        int lineWordCount = 0;
        while (cursor < n) {
            if (len + words[cursor].length() > maxWidth) {
                //当一行使用的单词长度加上一个词之后超出最大长度时，需要构建一行并重置lineWords和len
                result.add(buildNewLine(maxWidth, len, lineWords, lineWordCount));
                lineWordCount = 0;
                len = 0;
            } else {
                //当一行使用的单词长度加上一个词之后未超出最大长度时，这一行加上这个单词
                lineWords[lineWordCount++] = words[cursor];
                len += words[cursor].length() + 1;
                ++cursor;
            }
        }
        if (lineWordCount > 0) {
            //这一行还有剩余单词未处理
            result.add(buildNewLine(maxWidth, len, lineWords, lineWordCount));
        }
        //最后一行特殊处理
        String[] wordArr = result.remove(result.size() - 1).split(" ");
        StringBuilder lastLineBuilder = new StringBuilder(Arrays.stream(wordArr).filter(w -> w.length() > 0).collect(Collectors.joining(" ")));
        while (lastLineBuilder.length() < maxWidth) {
            lastLineBuilder.append(' ');
        }
        result.add(lastLineBuilder.toString());
        return result;
    }
    /**
     * 构建一行
     */
    private String buildNewLine(int maxWidth, int len, String[] lineWords, int lineWordCount) {
        if (lineWordCount < 2) {
            //一行只有一个单词，直接补充足够的空格
            String word = lineWords[0];
            int bCount = maxWidth - word.length();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < bCount; ++i) {
                sb.append(' ');
            }
            return word + sb.toString();
        }
        //一行多于一个单词时，先计算单词之间使用的空格数，最后这个+1是考虑到单词与单词之间最少要有1个空格
        int bCount = (maxWidth - len + 1) / (lineWordCount - 1) + 1;
        //但是可能存在不能整除的情况，此时需要计算余数，然后将余数平均分配到靠左侧的单词之间
        int remain = (maxWidth - len + 1) % (lineWordCount - 1);
        //构造一行
        StringBuilder sb = new StringBuilder();
        int k = 0;
        for (int i = 0; i < lineWordCount - 1; ++i) {
            //单词
            sb.append(lineWords[i]);
            //单词之间需要的空格数
            for (int j = 0; j < bCount; ++j) {
                sb.append(' ');
            }
            //未能整除时多出来的空格优先分配
            if (k < remain) {
                sb.append(' ');
                ++k;
            }
        }
        //一行的最后一个单词
        sb.append(lineWords[lineWordCount - 1]);
        return sb.toString();
    }

    /**
     * 228【模拟】汇总区间
     * 8 ms
     */
    public List<String> summaryRanges(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }
        List<String> result = new ArrayList<>();
        if (nums.length == 1) {
            result.add(nums[0] + "");
            return result;
        }
        int start = nums[0];
        int end = start;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == end + 1) {
                end = nums[i];
            } else {
                if (start < end) {
                    result.add(start + "->" + end);
                } else {
                    result.add(start + "");
                }
                start = nums[i];
                end = start;
            }
        }
        if (start >= end) {
            result.add(start + "");
        } else {
            result.add(start + "->" + end);
        }
        return result;
    }

    /**
     * 258【模拟】各位相加
     */
    public int addDigits(int num) {
        int sum;
        while (num > 9) {
            sum = 0;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            num = sum;
        }
        return num;
    }

    /**
     * 284【模拟】顶端迭代器
     */
    static class PeekingIterator implements Iterator<Integer> {

        private Iterator<Integer> it;

        private boolean peeked;

        private Integer next;

        public PeekingIterator(Iterator<Integer> iterator) {
            // initialize any member here.
            it = iterator;
            peeked = false;
            next = null;
        }

        // Returns the next element in the iteration without advancing the iterator.
        public Integer peek() {
            if (peeked) {
                return next;
            }
            next = it.next();
            peeked = true;
            return next;
        }

        // hasNext() and next() should behave the same as in the Iterator interface.
        // Override them if needed.
        @Override
        public Integer next() {
            if (peeked) {
                peeked = false;
                return next;
            }
            return it.next();
        }

        @Override
        public boolean hasNext() {
            if (peeked) {
                return true;
            }
            return it.hasNext();
        }
    }

    /**
     * 334【模拟】递增的三元子序列
     * 简单的模拟，先从原点开始，每次移动产生一条线段，记录下来，每次移动都将当前线段与之前所有线段做一次是否相交的比较
     * 但是这样会导致越往后比较的次数越来越多，题目数据范围是10^5，此方案复杂度是n^2，会令最终复杂度达到10^10，不可
     * 进阶，实际上经过画图归纳可知第i条线只可能与i-3、i-4、i-5这三条其中一条或多条交叉，只要判断其中一个相交就是相交
     * 如此，复杂度回落到n
     */
    public boolean isSelfCrossing(int[] distance) {
        int[][] DIRECTION = new int[][]{{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
        if (distance.length < 4) {
            return false;
        }
        //线段的上一个点
        int[] lastP = new int[]{0, 0};
        //最终产生的所有线段
        Line335[] lines = new Line335[distance.length];
        //标记使用第几个方向
        int dir = 0;
        for (int i = 0; i < distance.length; ++i) {
            //取当前方向
            int[] direction = DIRECTION[dir];
            //根据当前方向到达新的点
            int[] curP = new int[]{lastP[0] + direction[0] * distance[i], lastP[1] + direction[1] * distance[i]};
            //判断此线段是不是水平的
            boolean horizontal = direction[1] == 0;
            //from点的特征是x或y小于to对应的x或y
            int[] from, to;
            //判断哪个点做from，哪个点做to
            if (horizontal) {
                if (dir == 1) {
                    from = curP;
                    to = lastP;
                } else {
                    from = lastP;
                    to = curP;
                }
            } else {
                if (dir == 0) {
                    from = lastP;
                    to = curP;
                } else {
                    from = curP;
                    to = lastP;
                }
            }
            //生成新的线段
            lines[i] = new Line335(horizontal, from, to);
            //点迭代
            lastP = curP;
            //方向旋转至下一个迭代的方向
            ++dir;
            dir %= 4;
            //进行3种不同情况的线段相交检查
            if (i > 2) {
                if (isCross(lines[i], lines[i - 3])) {
                    return true;
                } else if (i > 3) {
                    if (isCross(lines[i], lines[i - 4])) {
                        return true;
                    } else if (i > 4) {
                        if (isCross(lines[i], lines[i - 5])) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
    /**
     * 表示线的模型，是否水平，并要求p1的x或y小于p2
     */
    static class Line335 {
        public boolean horizontal;
        public int[] p1;
        public int[] p2;

        public Line335(boolean horizontal, int[] p1, int[] p2) {
            this.horizontal = horizontal;
            this.p1 = p1;
            this.p2 = p2;
        }
    }
    /**
     * 判断两条线是否相交
     */
    private boolean isCross(Line335 line1, Line335 line2) {
        //情况一，十字形相交
        if (line2.p1[1] <= line1.p1[1] && line1.p1[1] <= line2.p2[1]) {
            if (line1.p1[0] <= line2.p1[0] && line2.p1[0] <= line1.p2[0]) {
                return true;
            }
        }
        //情况二，重合型相交
        if (line1.p1[0] == line2.p1[0]) {
            //纵向重合
            if (line2.p1[1] <= line1.p1[1] && line1.p1[1] <= line2.p2[1]) {
                return true;
            }
            if (line2.p1[1] <= line1.p2[1] && line1.p2[1] <= line2.p2[1]) {
                return true;
            }
        }
        if (line1.p1[1] == line2.p1[1]) {
            //横向重合
            if (line2.p1[0] <= line1.p1[0] && line1.p1[0] <= line2.p2[0]) {
                return true;
            }
            if (line2.p1[0] <= line1.p2[0] && line1.p2[0] <= line2.p2[0]) {
                return true;
            }
        }
        return false;
    }

    //722
    public List<String> removeComments(String[] source) {
        int n = source.length;
        List<String> result = new ArrayList<>(n);
        boolean commenting = false;
        StringBuilder buffer = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            String line = source[i];
            if (commenting) {
                int c3 = line.indexOf("*/");
                if (c3 < 0) {
                    continue;
                }
                commenting = false;
                line = line.substring(c3 + 2);
                source[i] = line;
                --i;
                continue;
            }
            //现在的line一定不在/**/这种注释里面
            int c1 = line.indexOf("//");
            int c2 = line.indexOf("/*");
            if (c1 >= 0 && (c2 < 0 || c1 < c2)) {
                //此时一定是//注释符号起作用
                line = line.substring(0, c1);
                buffer.append(line);
                if (buffer.length() > 0) {
                    result.add(buffer.toString());
                }
                buffer = new StringBuilder();
                continue;
            }
            if (c2 >= 0) {
                //此时一定是/*注释符号起作用
                int c3 = line.indexOf("*/", c2 + 2);
                if (c3 < 0) {
                    line = line.substring(0, c2);
                    buffer.append(line);
                    commenting = true;
                } else {
                    line = line.substring(0, c2) + line.substring(c3 + 2);
                    source[i] = line;
                    --i;
                }
                continue;
            }
            buffer.append(line);
            if (buffer.length() > 0) {
                result.add(buffer.toString());
            }
            buffer = new StringBuilder();
        }
        return result;
    }

    //p816
    public List<String> p816AmbiguousCoordinates(String s) {
        char[] charArr = s.toCharArray();
        List<String> result = new ArrayList<>();
        for (int i = 2; i < s.length() - 1; ++i) {
            List<String> plausibleX = possibleNumber(charArr, 1, i);
            List<String> plausibleY = possibleNumber(charArr, i, s.length() - 1);
            if (plausibleX.size() > 0 && plausibleY.size() > 0) {
                for (String x : plausibleX) {
                    for (String y : plausibleY) {
                        result.add("(" + x + ", " + y + ")");
                    }
                }
            }
        }
        return result;
    }

    private List<String> possibleNumber(char[] charArr, int from, int to) {
        List<String> plausible = new ArrayList<>();
        StringBuilder integer = new StringBuilder();
        integer.append(charArr[from]);
        StringBuilder decimal = new StringBuilder();
        for (int i = from + 1; i < to; ++i) {
            decimal.append(charArr[i]);
        }
        do {
            boolean numberValid = true;
            if (integer.length() > 1) {
                if (integer.charAt(0) == '0') {
                    numberValid = false;
                }
            }
            if (numberValid && decimal.length() > 0) {
                if (decimal.charAt(decimal.length() - 1) == '0') {
                    numberValid = false;
                }
            }
            if (numberValid) {
                if (decimal.length() > 0) {
                    plausible.add(integer + "." + decimal);
                } else {
                    plausible.add(integer.toString());
                }
            }
            if (decimal.length() > 0) {
                integer.append(decimal.charAt(0));
                decimal.deleteCharAt(0);
            } else {
                break;
            }
        } while (integer.length() <= to - from);
        return plausible;
    }

    /**
     * 1387【模拟】将整数按权重排序
     */
    public void helper1387() {
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(1, 0);
        for (int i = 2; i <= 1000; i++) {
            int w = 1, num = i;
            while (true) {
                int nextNum;
                if (num % 2 == 1) {
                    nextNum = 3 * num + 1;
                } else {
                    nextNum = num / 2;
                }
                Integer wi = dp.get(nextNum);
                if (null != wi) {
                    dp.put(i, wi + w);
                    break;
                }
                ++w;
                num = nextNum;
                if (num == 1) {
                    dp.put(i, w);
                    break;
                }
            }
        }
        for (int i = 1; i <= 1000; ++i) {
            System.out.printf("%d,", dp.get(i));
        }
    }
    private static final int[] WEIGHTS = new int[]{0,0,1,7,2,5,8,16,3,19,6,14,9,9,17,17,4,12,20,20,7,7,15,15,10,23,10,111,18,18,18,106,5,26,13,13,21,21,21,34,8,109,8,29,16,16,16,104,11,24,24,24,11,11,112,112,19,32,19,32,19,19,107,107,6,27,27,27,14,14,14,102,22,115,22,14,22,22,35,35,9,22,110,110,9,9,30,30,17,30,17,92,17,17,105,105,12,118,25,25,25,25,25,87,12,38,12,100,113,113,113,69,20,12,33,33,20,20,33,33,20,95,20,46,108,108,108,46,7,121,28,28,28,28,28,41,15,90,15,41,15,15,103,103,23,116,116,116,23,23,15,15,23,36,23,85,36,36,36,54,10,98,23,23,111,111,111,67,10,49,10,124,31,31,31,80,18,31,31,31,18,18,93,93,18,44,18,44,106,106,106,44,13,119,119,119,26,26,26,119,26,18,26,39,26,26,88,88,13,39,39,39,13,13,101,101,114,26,114,52,114,114,70,70,21,52,13,13,34,34,34,127,21,83,21,127,34,34,34,52,21,21,96,96,21,21,47,47,109,47,109,65,109,109,47,47,8,122,122,122,29,29,29,78,29,122,29,21,29,29,42,42,16,29,91,91,16,16,42,42,16,42,16,60,104,104,104,42,24,29,117,117,117,117,117,55,24,73,24,117,16,16,16,42,24,37,37,37,24,24,86,86,37,130,37,37,37,37,55,55,11,24,99,99,24,24,24,143,112,50,112,24,112,112,68,68,11,112,50,50,11,11,125,125,32,125,32,125,32,32,81,81,19,125,32,32,32,32,32,50,19,45,19,45,94,94,94,45,19,19,45,45,19,19,45,45,107,63,107,58,107,107,45,45,14,32,120,120,120,120,120,120,27,58,27,76,27,27,120,120,27,19,19,19,27,27,40,40,27,40,27,133,89,89,89,133,14,133,40,40,40,40,40,32,14,58,14,53,102,102,102,40,115,27,27,27,115,115,53,53,115,27,115,53,71,71,71,97,22,115,53,53,14,14,14,40,35,128,35,128,35,35,128,128,22,35,84,84,22,22,128,128,35,35,35,27,35,35,53,53,22,48,22,22,97,97,97,141,22,48,22,141,48,48,48,97,110,22,48,48,110,110,66,66,110,61,110,35,48,48,48,61,9,35,123,123,123,123,123,61,30,123,30,123,30,30,79,79,30,30,123,123,30,30,22,22,30,22,30,48,43,43,43,136,17,43,30,30,92,92,92,43,17,136,17,30,43,43,43,87,17,43,43,43,17,17,61,61,105,56,105,30,105,105,43,43,25,30,30,30,118,118,118,30,118,56,118,118,118,118,56,56,25,74,74,74,25,25,118,118,17,56,17,69,17,17,43,43,25,131,38,38,38,38,38,69,25,131,25,131,87,87,87,131,38,25,131,131,38,38,38,38,38,30,38,30,56,56,56,131,12,51,25,25,100,100,100,38,25,144,25,100,25,25,144,144,113,51,51,51,113,113,25,25,113,51,113,144,69,69,69,95,12,64,113,113,51,51,51,64,12,64,12,38,126,126,126,38,33,126,126,126,33,33,126,126,33,126,33,64,82,82,82,170,20,33,126,126,33,33,33,64,33,25,33,25,33,33,51,51,20,46,46,46,20,20,46,46,95,33,95,139,95,95,46,46,20,139,20,20,46,46,46,95,20,90,20,46,46,46,46,139,108,20,64,64,108,108,59,59,108,33,108,152,46,46,46,59,15,33,33,33,121,121,121,152,121,33,121,59,121,121,121,121,28,121,59,59,28,28,77,77,28,77,28,103,121,121,121,72,28,59,20,20,20,20,20,72,28,46,28,134,41,41,41,134,28,41,41,41,28,28,134,134,90,134,90,41,90,90,134,134,15,28,134,134,41,41,41,85,41,41,41,41,41,41,33,33,15,59,59,59,15,15,54,54,103,28,103,147,103,103,41,41,116,147,28,28,28,28,28,178,116,147,116,28,54,54,54,147,116,116,28,28,116,116,54,54,72,147,72,46,72,72,98,98,23,67,116,116,54,54,54,116,15,67,15,54,15,15,41,41,36,129,129,129,36,36,129,129,36,129,36,67,129,129,129,116,23,129,36,36,85,85,85,129,23,173,23,85,129,129,129,36,36,36,36,36,36,36,28,28,36,28,36,28,54,54,54,129,23,49,49,49,23,23,23,142,98,49,98,36,98,98,142,142,23,98,49,49,23,23,142,142,49,23,49,36,49,49,98,98,111,93,23,23,49,49,49,49,111};
    public int getKth(int lo, int hi, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[1] == b[1]) return a[0] - b[0];
            return a[1] - b[1];
        });
        for (int i = lo; i <= hi; ++i) {
            pq.offer(new int[]{i, WEIGHTS[i]});
        }
        for (int i = 0; i < k - 1; ++i) {
            pq.poll();
        }
        return pq.poll()[0];
    }

    //p1620
    public int[] p1620BestCoordinate(int[][] towers, int radius) {
        int maxX = 0, maxY = 0;
        for (int[] tower : towers) {
            maxX = Math.max(maxX, tower[0]);
            maxY = Math.max(maxY, tower[1]);
        }
        int[] candidate = new int[]{maxX, maxY};
        int strength = Integer.MIN_VALUE;
        for (int x = 0; x <= maxX; ++x) {
            for (int y = 0; y <= maxY; ++y) {
                int totalStrength = 0;
                for (int[] tower : towers) {
                    int deltaX = x - tower[0];
                    int deltaY = y - tower[1];
                    double euclideanDistance = Math.sqrt(deltaX * deltaX + deltaY * deltaY);
                    if (euclideanDistance <= radius) {
                        totalStrength += Math.floor(tower[2] / (1 + euclideanDistance));
                    }
                }
                if (totalStrength == strength) {
                    if (x < candidate[0] || (x == candidate[0] && y < candidate[1])) {
                        candidate = new int[]{x, y};
                    }
                } else if (totalStrength > strength) {
                    strength = totalStrength;
                    candidate = new int[]{x, y};
                }
            }
        }
        return candidate;
    }

    //p1669
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        int i = 0;
        //跳到第a个节点，找到需要保留的尾端cutTail
        ListNode cur1 = list1;
        ListNode prev1 = list1;
        while (i < a) {
            prev1 = cur1;
            cur1 = cur1.next;
            ++i;
        }
        ListNode cutTail = prev1;
        //跳过第b-a个节点，找到需要保留的头端tailHead
        while (i < b) {
            cur1 = cur1.next;
            ++i;
        }
        ListNode tailHead = cur1.next;
        //将新的链表链接到需要保留的两端，形成新的链表
        cutTail.next = list2;
        ListNode cur2 = list2;
        while (cur2.next != null) {
            cur2 = cur2.next;
        }
        cur2.next = tailHead;
        return list1;
    }

    //p1684
    public int countConsistentStrings(String allowed, String[] words) {
        boolean[] charAllowed = new boolean[26];
        for (char c : allowed.toCharArray()) {
            charAllowed[c - 'a'] = true;
        }
        int allowedCount = 0;
        for (String word : words) {
            boolean allow = true;
            for (char c : word.toCharArray()) {
                if (!charAllowed[c - 'a']) {
                    allow = false;
                    break;
                }
            }
            if (allow) {
                ++allowedCount;
            }
        }
        return allowedCount;
    }

    //p1704
    private static final boolean[] VOWEL = new boolean[26];
    static {
        VOWEL['a' - 'a'] = true;
        VOWEL['e' - 'a'] = true;
        VOWEL['i' - 'a'] = true;
        VOWEL['o' - 'a'] = true;
        VOWEL['u' - 'a'] = true;
    }

    public boolean p1704HalvesAreAlike(String s) {
        return countVowel(s, 0, s.length() / 2) == countVowel(s, s.length() / 2, s.length());
    }

    private int countVowel(String s, int from, int to) {
        int vowelCount = 0;
        for (int i = from; i < to; ++i) {
            char ch = s.charAt(i);
            int idx = Character.isLowerCase(ch) ? ch - 'a' : ch - 'A';
            if (VOWEL[idx]) {
                ++vowelCount;
            }
        }
        return vowelCount;
    }

    //p1732
    public int p1732largestAltitude(int[] gain) {
        int altitude = 0;
        int max = altitude;
        for (int j : gain) {
            altitude += j;
            max = Math.max(max, altitude);
        }
        return max;
    }

    //p1742
    public int p1742CountBalls(int lowLimit, int highLimit) {
        int d = 0, t = highLimit;
        while (t > 0) {
            ++d;
            t /= 10;
        }
        int[] counts = new int[9 * d + 1]; //highLimit最大为10^5，那么盒子的编号不会超过45，即如果highLimit位数为d，则最多不会超过9*d+1
        int maxCount = 0;
        for (int i = lowLimit; i <= highLimit; ++i) {
            int idx = 0;
            int x = i;
            while (x > 0) {
                idx += x % 10;
                x /= 10;
            }
            ++counts[idx];
            maxCount = Math.max(maxCount, counts[idx]);
        }
        return maxCount;
    }

    //p1748
    public int sumOfUnique(int[] nums) {
        int sum = 0;
        int[] buckets = new int[101];
        for (int num : nums) {
            if (buckets[num] == 0) {
                sum += num;
            } else if (buckets[num] == 1) {
                sum -= num;
            }
            ++buckets[num];
        }
        return sum;
    }

    //p1752
    public boolean check(int[] nums) {
        boolean descended = false;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i - 1] > nums[i]) {
                if (descended) {
                    return false;
                }
                descended = true;
            }
        }
        if (descended) {
            return nums[0] >= nums[nums.length - 1];
        }
        return true;
    }

    //p1758
    public int minOperations(String s) {
        int n = s.length();
        int zeroOperationCount = 0;
        for (int i = 0; i < n; ++i) {
            if ((i & 1) == 1) {
                if (s.charAt(i) != '1') {
                    ++zeroOperationCount;
                }
            } else {
                if (s.charAt(i) != '0') {
                    ++zeroOperationCount;
                }
            }
        }
        int oneOperationCount = 0;
        for (int i = 0; i < n; ++i) {
            if ((i & 1) == 1) {
                if (s.charAt(i) != '0') {
                    ++oneOperationCount;
                }
            } else {
                if (s.charAt(i) != '1') {
                    ++oneOperationCount;
                }
            }
        }
        return Math.min(zeroOperationCount, oneOperationCount);
    }

    //p1759
    public int countHomogenous(String s) {
        int mod = 1000000007;
        long res = 0L;
        char ch = s.charAt(0);
        int count = 1;
        int i = 1;
        for (; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == ch) {
                ++count;
            } else {
                long contribution = (1 + (long) count) * (long) count / 2;
                res += contribution;
                res %= mod;
                ch = c;
                count = 1;
            }
        }
        long contribution = (1 + (long) count) * (long) count / 2;
        res += contribution;
        res %= mod;
        return (int) res;
    }

    //p1768
    public String mergeAlternately(String word1, String word2) {
        int n = word2.length(), m = word1.length();
        int diff = Math.abs(m - n);
        StringBuilder spaces = new StringBuilder(diff);
        for (int i = 0; i < diff; ++i) {
            spaces.append(" ");
        }
        if (m > n) {
            word2 = word2 + spaces;
        } else if (m < n) {
            word1 = word1 + spaces;
        }
        n = word2.length();
        m = word1.length();
        StringBuilder res = new StringBuilder(n + m);
        for (int i = 0; i < word1.length(); ++i) {
            res.append(word1.charAt(i));
            res.append(word2.charAt(i));
        }
        return res.toString().replace(" ", "");
    }

    //p1769
    public int[] p1769MinOperations(String boxes) {
        int n = boxes.length();
        int[] result = new int[n];
        for (int i = 0; i < n; ++i) {
            int step = 0;
            for (int j = 0; j < n; ++j) {
                if (boxes.charAt(j) == '1') {
                    step += Math.abs(i - j);
                }
            }
            result[i] = step;
        }
        return result;
    }

    //p1773
    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        int matchCount = 0;
        int matchType = ruleKey.equals("type") ? 0 : (ruleKey.equals("color") ? 1 : 2);
        for (List<String> item : items) {
            if (ruleValue.equals(item.get(matchType))) {
                ++matchCount;
            }
        }
        return matchCount;
    }

    //p1779
    public int nearestValidPoint(int x, int y, int[][] points) {
        int result = -1;
        int minDis = Integer.MAX_VALUE;
        for (int i = points.length - 1; i >= 0; --i) {
            int[] point = points[i];
            if (x == point[0] || y == point[1]) {
                int dis = Math.abs(x - point[0]) + Math.abs(y - point[1]);
                if (minDis >= dis) {
                    minDis = dis;
                    result = i;
                }
            }
        }
        return result;
    }

    //1784
    public boolean checkOnesSegment(String s) {
        if ("0".equals(s)) {
            return true;
        }
        int state = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                if (state == 0) {
                    state = 1;
                } else if (state == 2) {
                    return false;
                }
            } else if (c == '0') {
                if (state == 1) {
                    state = 2;
                }
            }
        }
        return true;
    }

    //1790
    public boolean areAlmostEqual(String s1, String s2) {
        int difference = 0, n = s1.length();
        char d11 = 'a', d12 = 'a', d21 = 'a', d22 = 'a';
        for (int i = 0; i < n; ++i) {
            if (s1.charAt(i) != s2.charAt(i)) {
                ++difference;
                if (difference == 1) {
                    d11 = s1.charAt(i);
                    d21 = s2.charAt(i);
                } else if (difference == 2) {
                    d12 = s1.charAt(i);
                    d22 = s2.charAt(i);
                } else {
                    return false;
                }
            }
        }
        return d11 == d22 && d12 == d21;
    }

    //p1796
    public int secondHighest(String s) {
        int firstHighest = -1, secondHighest = -1;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                int d = ch - '0';
                if (d > firstHighest) {
                    secondHighest = firstHighest;
                    firstHighest = d;
                } else if (d != firstHighest && d > secondHighest) {
                    secondHighest = d;
                }
            }
        }
        return secondHighest;
    }

    //p1812
    public boolean squareIsWhite(String coordinates) {
        return !(((coordinates.charAt(0) - 'a') & 1) == ((coordinates.charAt(1) - '1') & 1));
    }

    //p1816
    public String truncateSentence(String s, int k) {
        int i = 0;
        for (; i < s.length() && k > 0; ++i) {
            char c = s.charAt(i);
            if (c == ' ') {
                --k;
            }
        }
        if (i < s.length()) {
            --i;
        }
        return s.substring(0, i);
    }

    //p1822
    public int arraySign(int[] nums) {
        boolean positive = true;
        for (int num : nums) {
            if (num == 0) {
                return 0;
            }
            if (num < 0) {
                positive = !positive;
            }
        }
        return positive ? 1 : -1;
    }

    //p1850
    public int numDifferentIntegers(String word) {
        Set<String> uniqueNumSet = new HashSet<>();
        StringBuilder numBuffer = new StringBuilder();
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            if (!Character.isDigit(ch)) {
                if (numBuffer.length() > 0) {
                    StringBuilder num = new StringBuilder();
                    int j = 0;
                    while (j < numBuffer.length() && numBuffer.charAt(j) == '0') {
                        ++j;
                    }
                    for (; j < numBuffer.length(); ++j) {
                        num.append(numBuffer.charAt(j));
                    }
                    if (num.length() < 1) {
                        num.append('0');
                    }
                    uniqueNumSet.add(num.toString());
                    numBuffer = new StringBuilder();
                }
            } else {
                numBuffer.append(ch);
            }
        }
        if (numBuffer.length() > 0) {
            StringBuilder num = new StringBuilder();
            int j = 0;
            while (j < numBuffer.length() && numBuffer.charAt(j) == '0') {
                ++j;
            }
            for (; j < numBuffer.length(); ++j) {
                num.append(numBuffer.charAt(j));
            }
            if (num.length() < 1) {
                num.append('0');
            }
            uniqueNumSet.add(num.toString());
        }
        return uniqueNumSet.size();
    }

    //p1995
    public int countQuadruplets(int[] nums) {
        int[] idxMap = new int[101];
        for (int i = 0; i < nums.length; ++i) {
            idxMap[nums[i]] = i;
        }
        int count = 0, sum = 0;
        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            for (int j = i + 1; j < nums.length; ++j) {
                sum += nums[j];
                for (int k = j + 1; k < nums.length; ++k) {
                    sum += nums[k];
                    if (sum <= 100 && idxMap[sum] > k) {
                        for (int l = k + 1; l < nums.length; ++l) {
                            if (nums[l] == sum) {
                                ++count;
                            }
                        }
                    }
                    sum -= nums[k];
                }
                sum -= nums[j];
            }
            sum -= nums[i];
        }
        return count;
    }

    //p2000
    public String reversePrefix(String word, char ch) {
        char[] charArr = word.toCharArray();
        int r = -1;
        for (int i = 0; i < charArr.length; ++i) {
            if (charArr[i] == ch) {
                r = i;
                break;
            }
        }
        if (r < 0) {
            return word;
        }
        int l = 0;
        while (l < r) {
            char c = charArr[r];
            charArr[r] = charArr[l];
            charArr[l] = c;
            ++l;
            --r;
        }
        return new String(charArr);
    }

    //p2016
    public int maximumDifference(int[] nums) {
        int min = nums[0], n = nums.length, maxDiff = -1;
        for (int i = 1; i < n; ++i) {
            min = Math.min(min, nums[i]);
            if (nums[i] > min) {
                maxDiff = Math.max(maxDiff, nums[i] - min);
            }
        }
        return maxDiff;
    }

    //p2027
    public int minimumMoves(String s) {
        int cnt = 0;
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == 'X') {
                ++cnt;
                i += 3;
            } else {
                ++i;
            }
        }
        return cnt;
    }

    //p2028
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int rollSum = 0;
        for (int roll : rolls) {
            rollSum += roll;
        }
        int missSum = (rolls.length + n) * mean - rollSum;
        if (missSum <= 0 || missSum > n * 6 || missSum < n) {
            return new int[0];
        }
        int per = missSum / n, remainder = missSum % n;
        int[] miss = new int[n];
        for (int i = 0; i < n; ++i) {
            miss[i] = per + (remainder > 0 ? 1 : 0);
            --remainder;
        }
        return miss;
    }

    //p2303
    public double calculateTax(int[][] brackets, int income) {
        double tax = 0.0;
        int prev = 0;
        double t;
        for (int i = 0; i < brackets.length; ++i) {
            if (income >= brackets[i][0]) {
                t = (double) (brackets[i][0] - prev) * brackets[i][1] / 100;
                tax += t;
            } else {
                t = (double) (income - prev) * brackets[i][1] / 100;
                tax += t;
                break;
            }
            prev = brackets[i][0];
        }
        return tax;
    }

    //p2042
    public boolean areNumbersAscending(String s) {
        String[] tokens = s.split(" ");
        int prevNumber = Integer.MIN_VALUE;
        for (String token : tokens) {
            if (Character.isDigit(token.charAt(0))) {
                int number = Integer.parseInt(token);
                if (number > prevNumber) {
                    prevNumber = number;
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    //p2047
    public int countValidWords(String sentence) {
        int wordCount = 0;
        char[] charArr = sentence.toCharArray();
        int l = 0, r = 0;
        while (l < charArr.length) {
            if (r <= charArr.length) {
                if (r == charArr.length || charArr[r] == ' ') {
                    boolean valid = r > l;
                    boolean joined = false;
                    for (int i = l; i < r; ++i) {
                        char c = charArr[i];
                        if (Character.isDigit(c)) {
                            valid = false;
                            break;
                        }
                        if (c == '!' || c == '.' || c == ',') {
                            if (i != r - 1) {
                                valid = false;
                                break;
                            }
                        }
                        if (c == '-') {
                            if (i == l || i == r - 1 || joined) {
                                valid = false;
                                break;
                            }
                            char c_ = charArr[i + 1];
                            if (i == r - 2 && (c_ == '!' || c_ == '.' || c_ == ',')) {
                                valid = false;
                                break;
                            }
                            joined = true;
                        }
                    }
                    if (valid) {
                        ++wordCount;
                    }
                    l = r + 1;
                }
            } else {
                l = r;
            }
            ++r;
        }
        return wordCount;
    }

    //p2104
    public long subArrayRanges(int[] nums) {
        long sum = 0L;
        int min, max;
        for (int i = 0; i < nums.length; ++i) {
            min = nums[i];
            max = nums[i];
            for (int j = i + 1; j < nums.length; ++j) {
                //找到每个子数组的范围，求和
                if (min > nums[j]) {
                    min = nums[j];
                }
                if (max < nums[j]) {
                    max = nums[j];
                }
                sum += max - min;
            }
        }
        return sum;
    }

    //p2283
    public boolean digitCount(String num) {
        int[] digitCount = new int[10];
        for (char ch : num.toCharArray()) {
            ++digitCount[ch - '0'];
        }
        for (int i = 0; i < num.length(); ++i) {
            if ((num.charAt(i) - '0') != digitCount[i]) {
                return false;
            }
        }
        return true;
    }

    //p2299
    public boolean strongPasswordCheckerII(String password) {
        if (password.length() < 8) {
            return false;
        }
        char prev = password.charAt(0);
        boolean lowerCase = Character.isLowerCase(prev);
        boolean upperCase = Character.isUpperCase(prev);
        boolean number = Character.isDigit(prev);
//        boolean special = prev == '!' || prev == '@' || prev == '#' || prev == '$' || prev == '%' || prev == '^' || prev == '&' || prev == '*' || prev == '(' || prev == ')' || prev == '+' || prev == '-';
        boolean special = (32 < prev && prev < 48) || prev == '^' || prev == '@';
        for (int i = 1; i < password.length(); ++i) {
            char cur = password.charAt(i);
            if (cur == prev) {
                return false;
            }
            if (!lowerCase) {
                lowerCase = Character.isLowerCase(cur);
            }
            if (!upperCase) {
                upperCase = Character.isUpperCase(cur);
            }
            if (!number) {
                number = Character.isDigit(cur);
            }
            if (!special) {
                special = (32 < cur && cur < 48) || cur == '^' || cur == '@';
            }
            prev = cur;
        }
        return lowerCase && upperCase && number && special;
    }

    //p2309
    public String greatestLetter(String s) {
        boolean[][] alphabetAppearance = new boolean[26][2];
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (Character.isUpperCase(ch)) {
                alphabetAppearance[ch - 'A'][0] = true;
            }
            if (Character.isLowerCase(ch)) {
                alphabetAppearance[ch - 'a'][1] = true;
            }
        }
        Character candidate = null;
        for (int i = 0; i < 26; ++i) {
            if (alphabetAppearance[i][0] && alphabetAppearance[i][1]) {
                candidate = (char) ('a' + i);
            }
        }
        if (null == candidate) {
            return "";
        }
        return String.valueOf(candidate).toUpperCase();
    }

    //2383
    public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
        int answer = 0;
        int totalEnergyConsumption = 0;
        for (int e : energy) {
            totalEnergyConsumption += e;
        }
        answer += totalEnergyConsumption + 1 - initialEnergy;
        if (answer < 0) answer = 0;
        int initTrainExp = experience[0] + 1 - initialExperience;
        initTrainExp = Math.max(0, initTrainExp);
        answer += initTrainExp;
        int experienceAccumulation = initialExperience + initTrainExp;
        for (int e : experience) {
            int train = Math.max(0, e + 1 - experienceAccumulation);
            answer += train;
            experienceAccumulation += e + train;
        }
        if (answer < 0) answer = 0;
        return answer;
    }

    /**
     * 2609【模拟+分类讨论】最长平衡子字符串
     * 只要遍历一次字符串就可以，时间复杂度O(n)；没有与s长度相关的数组空间，只有常量空间的变量，空间复杂度O(n)
     * 具体做法是每次遇到0的时候就记录下连续0的数量，然后遍历连续1的数量，两者取小的，再X2，得到题目要求的子串长度
     */
    public int findTheLongestBalancedSubstring(String s) {
        int answer = 0;
        int i = 0;
        char c;
        while (i < s.length()) {
            int zCnt = 0;
            c = s.charAt(i);
            if (c == '0') {
                //找到0，可能找到符合的子串，先遍历得到连续0的数量
                do {
                    c = s.charAt(i++);
                    if (c == '0') {
                        ++zCnt;
                    } else {
                        //由于c=1且i指针指向c的下一个字符位置，需要回退一下
                        --i;
                        break;
                    }
                } while (i < s.length());
            }
            //找出连续的1的长度
            int oCnt = 0;
            while (c == '1') {
                ++oCnt;
                ++i;
                if (i >= s.length()) break;
                c = s.charAt(i);
            }
            //符合题目要求的子串长度，取0和1部分较短的X2
            answer = Math.max(answer, Math.min(zCnt, oCnt) * 2);
        }
        return answer;
    }

    /**
     * 2735【枚举】收集巧克力
     */
    public long minCost(int[] nums, int x) {
        int n = nums.length;
        //记录每个下标在移动j次后的最小成本
        int[][] mnDp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            mnDp[i][0] = nums[i];
            for (int j = 1; j < n; ++j) {
                mnDp[i][j] = Math.min(mnDp[i][j - 1], nums[(i + j) % n]);
            }
        }
        //每一列数的和都是一次移动结果的枚举，取最小的结果
        long answer = 0;
        for (int i = 0; i < n; ++i) {
            answer += mnDp[i][0];
        }
        for (int j = 1; j < n; ++j) {
            //计算第j次移动时初始化就是j次的成本
            long t = (long) j * x;
            //然后计算一整列的结果，作为本次枚举的结果
            for (int i = 0; i < n; ++i) {
                t += mnDp[i][j];
            }
            answer = Math.min(answer, t);
        }
        return answer;
    }

    public static void main(String[] args) {
        SimulationSolution solution = new SimulationSolution();
        Assert.isTrue(7 == solution.getKth(7, 11, 4));
//        Assert.isTrue(13 == solution.minCost(new int[]{20,1,15}, 5));
    }
}
